package com.tucc.hello.leetcode.other;

import com.tucc.hello.leetcode.common.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode.other
 * @date 2021/6/7
 **/
public class ListNodeChange {


    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 4, 5);
//        change1(head);
//        ListNode newHead = reserve(head);
//        ListNode.print(newHead);
        change2(head);
        ListNode.print(head);
    }


    public static void change2(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode preSlow = null;
        ListNode fast = head.next.next;
        ListNode middle = null;
        while (fast != null) {
            preSlow = slow;
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                fast = fast.next;
                middle = slow;
            }
        }
        ListNode partRight = null;
        if (middle != null) {
            partRight = middle.next;
            preSlow.next = null;
            middle.next = null;
        } else {
            partRight = slow.next;
            slow.next = null;
        }

        ListNode reserveRight = reserve(partRight);
        ListNode left = head, right = reserveRight;
        ListNode temp = null;
        ListNode tempLeft, tempRight;
        while(left != null && right != null){
            tempLeft = left.next;
            tempRight = right.next;
            if(temp == null){
                temp = left;
            }
            else{
                temp.next = left;
                temp = temp.next;
            }
            temp.next = right;
            temp = temp.next;
            left = tempLeft;
            right = tempRight;
        }
        if(middle != null){
            temp.next = middle;
            temp.next.next = null;
        }
    }


    public static ListNode reserve(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reserve(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void change1(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode tail = head;
        while (tail != null) {
            list.add(tail);
            tail = tail.next;
        }
        int left = 0, right = list.size() - 1;
        ListNode temp = null;
        while (left < right) {
            if (temp == null) {
                temp = head;
                temp.next = list.get(right);
                temp = temp.next;
                temp.next = null;
            } else {
                temp.next = list.get(left);
                temp = temp.next;
                temp.next = list.get(right);
                temp = temp.next;
                temp.next = null;
            }
            left++;
            right--;
        }
        if (left == right) {
            temp.next = list.get(left);
            temp.next.next = null;
        }
    }


}
